
//2300.咒语和药水的成功对数
class Solution {

    int islower_bound(vector<int>& nums,int target)
    {
        int left=-1;
        int right=nums.size();
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid;
            else right=mid;
        }
        return right;
    }

public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        //使用二分
        //对potions进行排序，再枚举spell中每一个元素，看有多少种搭配
        int n=spells.size(),m=potions.size();
        sort(potions.begin(),potions.end());

        vector<int> ret(n);
        for(int i=0;i<n;i++)
        {
            long long target=(success-1+spells[i])/spells[i];  //向上取整
            if(target>potions.back()) ret[i]=0;
            else ret[i]=m-islower_bound(potions,target);
        }
        return ret;
    }
};